package test230602;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/6/2 12:29
 * 918. 环形子数组的最大和
 * https://leetcode.cn/problems/maximum-sum-circular-subarray/
 */
public class Solution02 {

    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;
        // f[i] 表示以 i 位置元素为结尾的最大子数组和
        // g[i] 表示以 i 位置为元素结尾的最小子数组和
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = g[0] = nums[0];
        int maxSum = f[0], minSum = g[0];  // 分别记录最大最小连续子数组和
        int sum = nums[0];  // 用于求整个数组的和, 由于 nums 是环形数组, 所以最大和也有可能是
        for (int i = 1; i < n; ++i) {
            f[i] = Math.max(f[i-1] + nums[i], nums[i]);
            g[i] = Math.min(g[i-1] + nums[i], nums[i]);
            sum += nums[i];
            maxSum = Math.max(maxSum, f[i]);
            minSum = Math.min(minSum, g[i]);
        }
        if (minSum == sum) {
            // 如果数组中全是负数
            return maxSum;
        }
        return Math.max(maxSum, sum - minSum);
    }
}
